Find Maximum in Sliding Window

Try to solve the Find Maximum in Sliding Window problem.

We'll cover the following

Statement#

Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.

Note: If the window size is greater than the array size, we consider the entire array as a single window.

Constraints:

  • 11 ≤\leq arr.length ≤\leq 10310^3
  • −104-10^4 ≤\leq arr[i] ≤\leq 10410^4
  • 11 ≤\leq w

Examples#

Created with Fabric.js 3.6.6 Output Input window size 3 nums -4 2 -5 3 6 Output 2 3 6 Sample example 1

1 of 3

Created with Fabric.js 3.6.6 Output Input nums 1 2 3 4 5 6 Output 6 window size 6 Sample example 2

2 of 3

Created with Fabric.js 3.6.6 Output Input nums 1 2 3 4 5 6 7 8 9 10 window size 4 Output 4 5 6 7 8 9 10 Sample example 3

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Find Maximum in Sliding Window

4

What should be the output if the following input is given?

nums = [1, 2, 3, 1, 4, 5, 2, 3, 6]

w = 3

Your Answer
A)

[2, 3, 5, 3]

B)

[3, 2, 4, 5, 5, 6]

Correct Answer
C)

[3, 3, 4, 5, 5, 5, 6]

Explanation

The first window of size 33 is [1, 2, 3], and the maximum in this window is 3. The second window of size 33 is [2, 3, 1], and the maximum in this window is also 3. The third window of size 33 is [3, 1, 4], and the maximum in this window is 4. The fourth window of size 33 is [1, 4, 5], and the maximum in this window is 5. The fifth window of size 33 is [4, 5, 2], and the maximum in this window is also 5. The sixth window of size 33 is [5, 2, 3], and the maximum in this window is also 5. The seventh and the last window of size 33 is [2, 3, 6], and the maximum in this window is 66.

D)

[1, 2, 3, 1, 4, 5, 2]

Question 4 of 44 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize an empty deque data structure.

Iterate through the the first w elements in the input array, performing cleanup operations on the deque to maintain a decreasing order of values.

Store the maximum value of the initial window.

Slide the window through the array, updating the deque and storing maximum values for each window.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Powered by AI
Input #1
Input #2
Find Maximum in Sliding Window

Solution: Repeated DNA Sequences

Solution: Find Maximum in Sliding Window